#include "tree.h"
#include<deque>
using namespace std;

TreeNode *Tree::getParent(TreeNode *node)
{
    return this->getParent(this,node);
}

TreeNode *Tree::getParent(Tree *t, TreeNode *node){
    deque<TreeNode*> que;
    que.push_back(t->root);
    if(t->root == node) return t->root;

    while(!que.empty()){
        TreeNode *nod = que.front();
        if(nod){
           // if(nod->getLeftChild()) que.push_back(nod->getLeftChild());
           // if(nod->getRightChild()) que.push_back(nod->getRightChild());
            if(nod->left){
                if(nod->left != node)
                    que.push_back(nod->left);
                else return nod;
            }

            if(nod->right)
                if(node->left != node)
                    que.push_back(nod->right);
                else return nod;
        }
    }
    return nullptr;
}

static int getDeep(TreeNode *node){
    if(node == nullptr) return 0;
    int left = getDeep(node->getLeftChild());
    int right = getDeep(node->getRightChild());
    return left > right? left+1 : right +1;
}
int Tree::getDeepth(Tree *t)
{
    if(t== nullptr) return -2;
    if(t->root == nullptr) return -1;
    return getDeep(t->root);
}

int Tree::getWidth(Tree *t)
{

}

